package com.hsogoo.study.leetcode.substring;

import java.util.HashMap;
import java.util.Map;

/**
 * 无重复字符的最长子串
 * 解法：滑动窗口+map存储
 * @Author huangsaigang
 * Created @2020-04-15.
 */
class Solution {

//    public static int lengthOfLongestSubstring(String s) {
//        if (s == null || "".equals(s)) {
//            return 0;
//        }
//        int max = 1;
//        Map<Character, Integer> positionMap = new HashMap<>();
//        for(int start=0, end= 0; end< s.length(); end++){
//            char current = s.charAt(end);
//            //如果之前已经存在
//            if(positionMap.containsKey(current)){
//                //防止start往前移动，abcdedafk
//                //移动到第二个d的时候start为3，移动到第二个a的时候a的下一位为1，这个时候不应该往前移动
//                start = Math.max(positionMap.get(current), start);
//            }
//            positionMap.put(current, end + 1);
//            max = Math.max(end - start + 1, max);
//        }
//        return max;
//    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }
        int max = 1;
        //用数组代替map
        int[] map = new int[128];
        int length = s.length();
        for(int start = 0, end= 0; end< length; end++){
            char current = s.charAt(end);
            //如果之前已经存在
            if(map[current -1] > 0){
                //防止start往前移动，abcdedafk
                //移动到第二个d的时候start为3，移动到第二个a的时候a的下一位为1，这个时候不应该往前移动
                start = Math.max(map[current -1], start);
            }
            map[current - 1] = end + 1;
            max = Math.max(end - start + 1, max);
        }
        return max;
    }

    public static void main(String[] args) {
        String s = "abcdedafk";
        System.out.println(lengthOfLongestSubstring(s));
    }
}